Programmable integrated circuit (IC) devices are a well-known type of IC that can be programmed to perform specified logic functions. One type of programmable IC, the field programmable gate array (FPGA), typically includes an array of programmable tiles. These programmable tiles can include, for example, input/output blocks (IOBs), configurable logic blocks (CLBs), dedicated block random access memories (BRAMs), multipliers, digital signal processing blocks (DSPs), processors, clock managers, delay lock loops (DLLs), and so forth.
Each programmable tile typically includes both programmable interconnect and programmable logic circuitry. The programmable interconnect circuitry typically includes a large number of interconnect lines of varying lengths interconnected by programmable interconnect points (PIPs). The programmable logic circuitry implements the logic of a user design using programmable elements that can include, for example, function generators, registers, arithmetic logic, and so forth.
The programmable interconnect and programmable logic circuits are typically programmed by loading a stream of configuration data into internal configuration memory cells that define how the programmable elements are configured. The configuration data can be read from memory (e.g., from an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
Another type of programmable IC is the complex programmable logic device, or CPLD. A CPLD includes two or more “function blocks” connected together and to input/output (I/O) resources by an interconnect switch matrix. Each function block of the CPLD includes a two-level AND/OR structure similar to those used in programmable logic arrays (PLAs) and programmable array logic (PAL) devices. In CPLDs, configuration data is stored on-chip in non-volatile memory. In other CPLDs, configuration data is stored on-chip in non-volatile memory, then downloaded to volatile memory as part of an initial configuration (programming) sequence.
For all of these programmable ICs, the functionality of the device is controlled by data bits provided to the device for that purpose. The data bits can be stored in volatile memory (e.g., static memory cells, as in FPGAs and some CPLDs), in non-volatile memory (e.g., FLASH memory, as in some CPLDs), or in any other type of memory cell.
Other programmable ICs are programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These programmable ICs are known as mask programmable devices. Programmable ICs can also be implemented in other ways, e.g., using fuse or antifuse technology. The phrase “programmable IC” can include, but is not limited to these devices and further can encompass devices that are only partially programmable. For example, one type of programmable IC includes a combination of hard-coded transistor logic and a programmable switch fabric that programmably interconnects the hard-coded transistor logic.
A circuit design, in general, is implemented within a programmable IC by performing an implementation flow comprising a plurality of tasks. An electronic design automation (EDA) tool or tools, as the case may be, performs the implementation flow. In general, the tasks performed during an implementation flow by the EDA tool include synthesis, mapping, placement, and routing. Performing the implementation flow allows the circuit design to be implemented within a particular programmable IC referred to as the target programmable IC.
Synthesis generally refers to the process of converting a hardware description language (HDL) description of a circuit design into a gate level description of the circuit design. The circuit design can be “compiled” using a logic synthesis tool into an implementation of low level logic gates. Mapping generally refers to the process of identifying constructs of the logical netlist, e.g., primitive logic gates, and associating those constructs with the physical resources of the target programmable IC that can implement the constructs. For example, one or more individual logic gates may be mapped to look-up tables (LUTs), latches, flip-flops, BRAMs, or the like.
Placement generally refers to the process of assigning the types of physical resources, to which constructs of the synthesized circuit design have been mapped, to actual locations on the target programmable IC. For example, once logic gates are assigned to LUTs for implementation, combinations of logic gates can be assigned to a particular LUT on the target programmable IC, where that LUT has a particular, physical location on the target programmable IC.
Routing a circuit design refers to the process of programming the interconnect circuitry to establish the necessary signaling links among the various physical resources, e.g., circuit elements of the target programmable IC. Routing can be a complicated process due to the large number of nets that must be processed, the large number of PIPs, and the necessity of avoiding conflicting assignments of nets to PIPs, all while trying to meet design goals relating to performance and power consumption. Despite much research in this field, routing a circuit design still can take a significant amount of time.
The advent of multi-processor computing systems provides the opportunity to perform tasks in parallel, thereby facilitating more efficient and faster operation of EDA tools than on single processor systems. To take advantage of the parallelism of multi-processor systems and reduce runtimes, EDA tools often must be redesigned. Conventional techniques for performing tasks such as routing, for example, when applied to multi-processor computing systems may be non-deterministic. More particularly, the EDA tool, in many cases, is unable to reliably reproduce a given solution to a particular problem. Thus, each time the EDA tool is run on a given circuit design, a different routing result may be generated. This non-determinism within the EDA tool makes supporting commercial users difficult since prior results cannot be reliably reproduced.